package linkedlist.josephus;

/**
 * @author : Rookie
 * @description :  约瑟夫环 链表解法
 * @date : 2023/5/15
 */
public class JosephusCircle {

    public static void main(String[] args) {
        josephus(20,5);
    }

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    /**
     * 约瑟夫环问题解决
     * @param n 总人数
     * @param m 第几个出列
     */
    public static void josephus(int n,int m) {

        StringBuilder sb = new StringBuilder();

        Node head = new Node(1);
        Node prev = head;
        for (int i = 2; i <= n ; i++) {
            Node currNode = new Node(i);
            prev = currNode;
        }
        // 链表尾指向头 形成循环链表
        prev.next = head;

        Node p1 = head;
        Node p2 = head;

        while (p1.next != p1) {
            int count = 1;
            // 当 ptr1 指向要被删除的节点时，我们将 ptr2 的 next 指向它的下一个节点，并将 ptr1 指向 ptr2 的下一个节点以便继续遍历。
            while (count != m) {
                p2 = p1;
                p1 = p1.next;
                count ++;
            }
            sb.append(p1.val).append(" ");
            p2.next = p1.next;
            p1 = p2.next;
        }

        sb.append(p1.val);
        System.out.println("出列顺序： " + sb);
    }
}
